#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> res;
        int curCntMap[26] = { 0 };
        int aimCntMap[26] = { 0 };
        int curCnt = 0;
        for (char ch : p) { aimCntMap[ch - 'a']++; }
        int n = p.size();
        int left = 0, right = 0;
        while (right < s.size())
        {
            // in
            if (right - left < n)
            {
                curCntMap[s[right] - 'a']++;
                if (curCntMap[s[right] - 'a'] <= aimCntMap[s[right] - 'a']) {
                    ++curCnt;
                }
            }
            // judge
            if (right - left + 1 == n)
            {
                if (curCnt == n) { res.push_back(left); }// update
                // out
                if (curCntMap[s[left] - 'a'] <= aimCntMap[s[left] - 'a']) {
                    --curCnt;
                }
                curCntMap[s[left++] - 'a']--;
            }
            ++right;
        }
        return res;
    }
};

int main()
{
   Solution s;
   vector<int> res = s.findAnagrams("cbaebabacd", "abc");
   for (auto e : res) {
      cout << e << endl;
   }
   return 0;
}
